package 简单.二分查找;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 写一个 RecentCounter 类来计算特定时间范围内最近的请求。
 * 请你实现 RecentCounter 类：
 * RecentCounter() 初始化计数器，请求数为 0 。
 * int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为
 * 单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）
 * 。确切地说，返回在 [t-3000, t] 内发生的请求数。
 * 保证 每次对 ping 的调用都使用比之前更大的 t 值。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/number-of-recent-calls
 */
public class 最近的请求次数_933 {

    public static void main(String[] args) {

        RecentCounter2 recentCounter = new RecentCounter2();
        System.out.println(recentCounter.ping(1));
        System.out.println(recentCounter.ping(100));
        System.out.println(recentCounter.ping(3001));
        System.out.println(recentCounter.ping(3002));

    }


}

/**
 * 列表+二分查找
 */
class RecentCounter {

    List<Integer> list = new ArrayList<>();

    private int efficientLeft = 0;

    public RecentCounter() {

    }

    public int ping(int t) {
        list.add(t);
        return list.size() - search(t - 3000);
    }

    private int search(int target) {
        int left = efficientLeft, right = list.size() - 1, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int curNum = list.get(mid);
            if (curNum >= target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        efficientLeft = ans;
        return ans;
    }
}

/**
 * 双端队列+模拟
 */
class RecentCounter2 {

    private Deque<Integer> deque = new ArrayDeque<>();

    public RecentCounter2() {

    }

    public int ping(int t) {
        deque.addLast(t);
        while (deque.peekFirst() < t - 3000) {
            deque.pollFirst();
        }
        return deque.size();
    }
}
